/**
  题目:
      实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

      如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

      必须原地修改，只允许使用额外常数空间。

      以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
      1,2,3 → 1,3,2
      3,2,1 → 1,2,3
      1,1,5 → 1,5,1

 链接：
    https://leetcode-cn.com/problems/next-permutation   
  思路:
    条件1.求一个比原序列字典序更大的序列
    条件2.并且字典序变大的增量要尽量的小
    以[5,6,11,9,7,5,3,1]举例吧

    1.首先从尾部查找，直到找到当前元素大于前一个元素为止，记录该位置；
    对于[5,6,11,9,7,5,3,1]，即查找到11>6，此时位置索引为2；
    2.从该位置到数组尾部的子序列中，找到一个比前一位置的大且最接近的数；
    对于[5,6,11,9,7,5,3,1]，即在[11,9,7,5,3,1]找到7，7是比6大且最接近6的，从尾部开始遍历，遍历到大于6的索引即可；
    3.将找到的数与前一位置的数交换；
    对于[5,6,11,9,7,5,3,1]，交换后变为[5,7,11,9,6,5,3,1]；
    4.将该位置到数组尾部的子序列进行升序排列，因为已经为降序，故首尾两两交换即可；
    对于步骤3中的[5,7,11,9,6,5,3,1],交换后为[5,7,1,3,5,6,9,11]；

    注意：
    对于最大的排列，从小到大排列即可；
 
       
  效果:
    执行用时：8 ms, 在所有 C++ 提交中击败了65.96%的用户
    内存消耗：11.9 MB, 在所有 C++ 提交中击败了62.29%的用户
*/ 



class Solution {
public:
    void nextPermutation(vector<int>& nums) {
       if(!nums.size()) return;
        int maxv=INT_MIN,i;
        for(i=nums.size()-1;i>=0;i--)
        {
            if(nums[i]<maxv) break;
            maxv=max(maxv,nums[i]);
        }
        if(i<0)
        {
            reverse(nums.begin(),nums.end());
            return;
        }
        int minv=INT_MAX,j,u=-1;
        for(j=i+1;j<nums.size();j++)
            if(nums[j]>nums[i]&&nums[j]<minv)  minv=nums[j],u=j;
        swap(nums[i],nums[u]);
        sort(nums.begin()+i+1,nums.end());
        return;
 
    }
};